Databases may reside in mobile devices, and often times the data stored in these databases is a replica of another database, stored in a less mobile location, such as a desktop computer or an enterprise data server. Because mobile devices are not always connected, they are typically synchronized with the other replicas on a periodic basis. Synchronization may be performed transactionally or using merge replication, for example. This exchange of information is commonly bi-directional: data is sent in and out of the databases. In order to minimize the time spent processing the data and sending it over the network, most synchronization protocols only send the changes since the last communication between the databases.
Because communication may be expensive in both monetary and performance terms, it is desirable to efficiently detect the changes that are to be sent.